The present invention relates to a dynamically self-configuring, directed token passing local area network. A local area network is referred to herein as "LAN" or "network". More particularly, the present invention pertains to improvements in such LANs which increase the logical limit of the number of nodes which can be operative on the network, and which allow all of the nodes, including additional nodes, to be established in a token passing loop, on a self-configuring and dynamic basis.
In general, a LAN is a communication medium and means by which a relatively large number of relatively closely physically located processor-based communications devices can send and receive message communications. The medium usually includes electrical or optical cables, but may also include radio or open-air optical links over which signals are conducted. Each communication device and its interconnection to the medium is referred to as a "node". Messages are communicated by transmitting patterns of signal elements, known as frames, between nodes. Each node of the LAN has its own unique adress or identification (ID). Typically, a frame includes address information of the transmitting or source node, known as the source ID or SID, and address information of the destination node to which the frame is addressed, known as the destination ID or DID. The transmitted frames are disregarded by all nodes except the destination node, but each node decodes the DID of the frame to the extent necessary to determine whether the frame is addressed to it.
Access to the LAN medium is controlled to assure that only one message is properly communicated at a time, thereby preventing two or more nodes from simultaneously transmitting frames and interferring with one another and with the proper operation of the LAN. One widely used technique of medium access control involves a "token". A token is a frame which is addressed to a specific destination node and which, upon receipt at the destination node, allows that node to have the exclusive right to initiate a message communication over the medium. The operational protocol of the LAN permits only the node in receipt of the token to initiate the message communication. Since the LAN typically uses only one token, there is no interference resulting from the simultaneous initiation of multiple message communications because only the node in receipt of the token can initiate message communications.
The operational protocal of the LAN causes the token to be passed among all of the active nodes in a regular, complete and even rotational pattern or sequence, called a "token loop" or a "token passing loop". The token loop allows each active node to have equal access to the medium for initiating message communications. Each active node receives the token in its turn in the token loop, regardless of whether or not that node has a message communication to initiate. If the node has a message communication to initiate, it does so after receipt of the token, and then passes the token to the next node in the loop after communication of the message has been completed. If the node does not have a message communication to initiate, the token is immediately passed to the next node in the token loop.
Another type of LAN access control is contention arbitration or Carrier-Sense Multiple Access (predominantly CSMA/CD). With contention arbitration only those nodes which have messages to communicate vie for access to the LAN medium. When a node with a message to communicate detects that no other message communication is in progress over the medium, it initiates the message communication. So long as no other node also initiates a message simultaneously, the node which is first in time receives exclusive access to the LAN medium for the duration of its message. If two or more nodes initiate message communications simultaneously, a collision of the transmitted signals occurs and prevents the colliding messages from being correctly delivered. Collisions necessitate subsequent re-transmissions of the collided message communications. Thus, in contention arbitrated LANs, each node must contend with all other nodes for access to the LAN medium. Contention-type LANs are not pertinent to the present invention, because contention-type LANs do not utilize tokens and the present invention pertains to token based LANs.
LANs can further be distinguished by the signal connectivity or signal transmission patterns. Bus-type LANs connect all nodes to a single common logical or electrical point, although the single common point may be physically dispersed over a large number of locations. Bus-type LANs send signals directly from the source node to the destination node, through the common connection point. The transmitted signals from any node are received about simultaneously by all the other nodes and are disregarded by all of the nodes except the destination node. Since all signals are transmitted and received through a common connection point, the communication path between all the nodes of a bus-type LAN is bi-directional, usually half-duplex.
Ring-type LANs have all of their nodes physically connected in a serial loop or ring. Each node always transmits to its neighboring node in the ring and receives from its other neighboring node in the ring. All the nodes in the ring serially pass the uni-directional transmissions from one to another in this ring. The signals are sent through every intervening connected node in the ring between the source node and the destination node. All of the nodes operate in synchronism, with each node receiving and re-transmitting the signal. The address information contained within the transmission causes only the destination node to utilize the information, while the other nodes simply pass the message on to their neighboring nodes in the ring. Thus, all transmissions in a ring-type LAN circulate in an unalterable, predefined, unidirectional signal path through all of the nodes around the ring. When tokens are employed in a ring-type LAN, the tokens are also passed in a logical sequence which is the same as the unalterable ring-like physical path.
The concept of "directed-token" applies to networks where the recipient of a token is determined by a destination address or DID in the token frame. A directed token approach is primarily used on token bus networks, where there is a logical token passing loop operating on a physical bus. This technique can also be used on other broadcast-media networks such as radio-frequency or free-air optical links. In contrast, token passing on token-based ring networks is not of the "directed-token" variety, because the token is passed by the physical transmission of the token frame from one node to the next adjacent node in the ring. The sequence of token passing on a ring is the physical connection order of nodes in the ring. As a result, token frames on token-based rings generally do not include a destination address. Bus-structured networks and broadcast-media networks do not have a physical means of designating the destination of a token pass and therefore incorporate a destination address in each token. In general, the improvements of the present invention are not readily applicable to token-based ring LANs.
In some situations it becomes desirable to connect a large number of nodes to the LAN. The maximum number of nodes on a LAN is due to either physical or logical restrictions. The physical restrictions pertain to electrical and/or cabling limits, as required by or for signal propagation and decay. The logical restrictions relate to how many nodes may be addressed in the node addressing scheme of the LAN operational protocol. As a physical restriction, a LAN bus which is wired as a single multi-drop cable is limited in the number of drops which may be installed on a cable segment, but a LAN bus which is wired as an unrooted tree has little or no practical limit on the physical number of nodes that may be attached, other than as is limited by the maximum end-to-end signal propagation delays which can be tolerated by the network operating protocol. A ring network has a physical limit on the number of allowed nodes based upon the maximum amount of synchronization fluctuation or clock "jitter" that is acceptable for the data recovery circuits of the node receivers. A small amount of time-base clock jitter accumulates at each node of the ring, which causes a practical limit on the number of nodes on the ring.
As a logical restriction, IEEE 802.3-type bus networks (e.g., contention arbitrated) are not practically limited in the logical number of nodes, since their address fields are 48 bits long, permitting roughly 144 trillion distinct node addresses. On the other hand, most non-IEEE 802 bus networks use address fields in the frames that are only 8 bits long. An 8-bit length of the address field limits the number of nodes and addresses to no more than 255, since each node requires its own separate address. Increasing the size of the address field to accommodate more than 255 nodes might be possible, but the network operating protocol will usually not accommodate expanded address fields.
Increasing the size of a directed token passing network by adding more nodes and expanding the address field without replacing the pre-existing nodes is not a complete solution to expanding the size of the network, because the network operating protocol does not allow the additional nodes at the expanded addresses to be dynamically configured or reconfigured in the token passing loop. Reconfiguration, as explained in greater detail below, is that process whereby all the active nodes are automatically and dynamically established in the token passing loop. The reconfiguration sequence under the standard or basic network operating protocol is effective only as to the nodes in the basic range of standard addresses and not to additional nodes in an extended or expanded range of addresses. All of the active nodes must be included in the token loop for the network to function properly. Replacing numerous pre-existing nodes in order to use expanded address space is economically unattractive.
Accommodating the basic network operating protocol for reconfiguration while still incorporating in the reconfiguration sequence those additional nodes at an expanded range of addresses beyond the original limit established by the basic address field, is believed to have been a significant impediment to expanding the size of a directed token LAN, prior to the present invention.